public class IsMatch {
    public boolean isMatch(String s, String p) {
        // 状态表示：dp[i][j]表示p字符串[0,j]之间的字符串是否能够匹配s字符串[0,i]之间的字符串
        // 状态转移方程：同样是根据最后一个位置来推导
        // 对于p字符串来说，最后一个字符可能有三种情况：
        // 1. 为a~z的字符，那么 dp[i][j] = (s[i] == p[j] && dp[i-1][j-1])
        // 2. 为.，因为 . 可以匹配任意一个字符，所以dp[i][j] = dp[i-1][j-1]
        // 3. 为 *，因为 * 可以匹配零个或多个前面的那一个元素，那么对于 * 前面的元素也是有两种情况的
        //    1. * 之前的字符p[j-1]为 .，那么也就是说 .* 可以匹配零个或者多个任意字符
        //       当匹配零个字符的时候，dp[i][j] = dp[i][j-2]
        //       当匹配一个字符的时候，dp[i][j] = dp[i-1][j-2]，两个dp[i][j] = dp[i-2][j-2]、dp[i-3][j-2]、dp[i-n][j-2],也就是说这种情况下dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-2][j-2]...
        //       上面的dp[i][j]可以简化为：dp[i-1][j] = dp[i-1][j-2] || dp[i-2][j-2]...
        //       这种情况下的dp[i][j]就简化为了dp[i][j-2] || dp[i-1][j]
        //    2. p[j-1]为a~z的字符,那么[a~z]*就可以匹配零个或者多个p[j-1]个字符了
        //       当匹配零个字符的时候,dp[i][j] = dp[i][j-2]
        //       匹配一个字符的时候，dp[i][j] = (s[i] == p[i-1] && dp[i-1][j-2])
        //       两个 dp[i][j] = (s[i] == p[i-1] && s[i-1] == p[i-2] && dp[i-2][j-3])
        //       可以简化为dp[i][j] = dp[i][j-2] || (c[i] == p[j-1] && dp[i-1][j])

        // 初始化，这里在填表的时候需要用到i-1、j-1和j-2，那么这里我们在创建dp表的时候只需要多创建出一行和一列
        // 就可以了，为什么呢？这里不是还使用到了j-2吗，只多一列不是会越界吗？不会的，因为题目中说了
        // 保证每次出现字符 * 时，前面都匹配到有效的字符，也就是说当出现*的时候，前面至少会有一个字符
        // 那么只多创建一列是不会出现越界的情况的
        s = " " + s;
        p = " " + p;
        char[] c1 = s.toCharArray();
        char[] c2 = p.toCharArray();
        boolean[][] dp = new boolean[c1.length][c2.length];
        // 初始化
        // 当s字符串为空串的时候，那么只有当p串可以匹配空串的时候才可以，那么什么情况下会匹配空串呢
        // 当p串为 _* 或者连续多个 _* 的时候是可以匹配空串的
        for (int j = 2; j < c2.length; j += 2) {
            if (c2[j] == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }
        // 当p串为空串的时候，除了s也为空串的时候是可以匹配的，其他情况下是无法匹配的
        dp[0][0] = true;
        // 填表顺序，因为需要使用到dp[i-1][j-1]、dp[i][j-2]、dp[i-1][j]，所以填表顺序是从上往下、从左往右
        for (int i = 1; i < c1.length; i++) {
            for (int j = 1; j < c2.length; j++) {
                if (c2[j] >= 'a' && c2[j] <= 'z') {
                    dp[i][j] = (c1[i] == c2[j] && dp[i-1][j-1]);
                } else if (c2[j] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (c2[j] == '*') {
                    if (c2[j-1] >= 'a' && c2[j-1] <= 'z') {
                        dp[i][j] = dp[i][j-2] || (c1[i] == c2[j-1] && dp[i-1][j]);
                    } else {
                        dp[i][j] = dp[i][j-2] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[c1.length-1][c2.length-1];
    }

    public static void main(String[] args) {
        IsMatch isMatch = new IsMatch();
        System.out.println(isMatch.isMatch("aa", "a*"));
    }
}
